Arbitration of resources is often required in circuits and systems. Sometimes arbitration is required where multiple entities are attempting to gain access to another entity and there is insufficient bandwidth to handle all the resource requests simultaneously. This presents a problem.
For example, in devices and applications using the PCI Express Bus™, the PCI Express specification provides for arbitration of Virtual Channels (VCs). (PCI Express and PCI-SIG are trademarks of PCI-SIG.)
As an arbitration table grows in size the resulting hierarchy of comparators required in hardware to form a state machine grows in an order of magnitude (big Oh) other than linear. Thus many more gates are needed to implement a state machine as the arbitration table grows in size, additionally, the additional gates and/or machine states, have associated delays and so arbitration latency may be affected. This presents a problem.
The PCI Express™ Base Specification Revision 1.1 dated Mar. 28, 2005 (“PCIe Spec”) is hereby incorporated by reference.
RR denotes Round Robin. WRR denotes Weighted Round Robin. VC denotes Virtual Channel. RCRB denotes Root Complex Register Block.
Port Arbitration Table functionality as stated/described in PCI Express Base Specification Rev1.1 is (PCIe Spec at 7.11.10):
The Port Arbitration Table register is a read-write register array that is used to store the WRR or time-based WRR arbitration table for Port Arbitration for the VC resource. This register array is valid for all Switch Ports, Root Ports that support peer to peer traffic, and RCRBs, but not for Endpoint devices. It is only present when one or more asserted bits in the Port Arbitration Capability field indicate that the device supports a Port Arbitration scheme that uses a programmable arbitration table. Furthermore, it is only valid when one of the above mentioned bits in the Port Arbitration Capability field is selected by the Port Arbitration Select field.
The Port Arbitration Table represents one Port arbitration period. FIG. 7-48 shows the structure of an example Port Arbitration Table with 128 phases and 2-bit table entries. Each table entry containing a Port Number corresponds to a phase within a Port arbitration period. For example, a table with 2-bit entries can be used by a Switch component with up to four Ports. A Port Number written to a table entry indicates that the phase within the Port Arbitration period is assigned to the selected PCI Express Port (the Port Number must be a valid one).
When the WRR Port Arbitration is used for a VC of any Egress Port, at each arbitration phase, the Port Arbiter serves one transaction from the Ingress Port indicated by the Port Number of the current phase. When finished, it immediately advances to the next phase. A phase is skipped, i.e., the Port Arbiter simply moves to the next phase without delay, if the Ingress Port indicated by the phase does not contain any transaction for the VC (note that a phase cannot contain the Egress Port's Port Number).
When the Time-based WRR Port Arbitration is used for a VC of any given Port, at each arbitration phase aligning to a virtual timeslot, the Port Arbiter serves one transaction from the Ingress Port indicated by the Port Number of the current phase. It advances to the next phase at the next virtual timeslot. A phase indicates an “idle” timeslot, i.e., the Port Arbiter does not serve any transaction during the phase, if                the phase contains the Egress Port's Port Number, or        the Ingress Port indicated by the phase does not contain any transaction for the VC.The Port Arbitration Table Entry Size field in the Port VC Capability register determines the table entry size. The length of the table is determined by the Port Arbitration Select field as shown in Table 7-45.When the Port Arbitration Table is used by the default Port Arbitration for the default VC, the default values for the table entries must contain at least one entry for each of the other PCI Express Ports of the device to ensure forward progress for the default VC for each Port. The table may contain RR or RR-like fair Port Arbitration for the default VC.        
For example, FIG. 3 illustrates an approach 300 as shown in the PCI Express™ Base Specification Revision 1.1 dated Mar. 28, 2005 at page 434 in FIG. 7-48: Example Port Arbitration Table with 128 Phases and 2-bit Table Entries and Table 7-45: Length of Port Arbitration Table. As may be seen the table can grow in size as well as the table entries may grow in size.
For example, FIG. 4 illustrates a current approach for a Port Arbitration Table with 32 Phases and 3 bits (i.e. 8 ports addressable). In this example, the Phase and corresponding port for that phase are shown. The phase thus indicates the next Ingress Port. If the Ingress Port indicated by the phase did not contain any transaction for the VC, then in the worst possible scenario it would have to skip 31 phases to select the Ingress Port which was able to proceed. This adds extra latency (e.g. clock cycles) to the implementation. For example, in FIG. 4, assume that at Phase 0 port 2 has two transactions to process, and all other ports have no transaction for the VC, then it can process one transaction at Phase 0, however, it must then step through all other phases (Phase 1-31) before it can process the second transaction. This presents a problem.